package com.desin.modle.datastruct.algo.DynamicAlgorithm.zeroOnePackage;

public class Solution1 {
    public int test1(int[] weights,int maxNum,int maxWeight){
        boolean[][] states = new boolean[maxNum][maxWeight+1];

        states[0][0] = true;

        if(weights[0]<maxWeight){
            states[0][weights[0]]=true;
        }

        for(int i=1;i<maxNum;i++){
            for(int j=0;j<=maxWeight;j++){
                if(states[i-1][j]){
                    states[i][j] = states[i-1][j];
                }
            }
            for (int j=0;j<=maxWeight-weights[i];j++){
                if(states[i-1][j]){
                    states[i][j+weights[i]]=true;
                }
            }
        }

        for(int i=maxWeight;i>=0;i--){
            if(states[maxNum-1][i]){
                return i;
            }
        }
        return 0;
    }

    public int test2(int[] weights,int maxNum,int maxWeight){
        boolean[] states = new boolean[maxWeight+1];

        states[0] = true;
        if(weights[0]<maxWeight){
            states[weights[0]] = true;
        }
        for(int i=1;i<maxNum;i++){
            for(int j=maxWeight-weights[i];j>=0;j--){
                if(states[j]){
                    states[j+weights[i]]=states[j];
                }
            }
        }
        for(int i=maxWeight;i>=0;i--){
            if(states[i]){
                return i;
            }
        }
        return 0;
    }

    public int test3(int[] weights,int[] values,int maxNum,int maxWeight){
        int[][] states = new int[maxNum][maxWeight+1];
        for(int i=0;i<maxNum;i++){
            for(int j=0;j<=maxWeight;j++){
                states[i][j]=-1;
            }
        }

        states[0][0] = 0;
        if(weights[0]<maxWeight){
            states[0][weights[0]]=values[0];
        }
        for(int i=1;i<maxNum;i++){
            for(int j=0;j<=maxWeight;j++){
                if(states[i-1][j]>=0){
                    states[i][j]=states[i-1][j];
                }
            }
            for(int j=0;j<=maxWeight-weights[i];j++){
                if(states[i-1][j]>=0){
                    int v=states[i-1][j]+values[i];
                    if(v>states[i][j+weights[i]]){
                        states[i][j+weights[i]] = v;
                    }
                }
            }
        }
        int resultValue = -1;
        for(int i=maxWeight;i>=0;i--){
            int v = states[maxNum-1][i];
            if(v>resultValue){
                resultValue = v;
            }
        }
        return resultValue;
    }

    public void test4(int[] items,int maxNum,int manJian){
        boolean[][] states = new boolean[maxNum][3*manJian+1];
        states[0][0] = true;
        int maxValue = 3 * manJian;
        if(items[0]<maxValue){
            states[0][items[0]]=true;
        }

        for(int i=1;i<maxNum;i++){
            for(int j=0;j<=maxValue;j++){
                if(states[i-1][j]){
                    states[i][j]=states[i-1][j];
                }
            }
            for(int j=0;j<=maxValue-items[i];j++){
                if(states[i-1][j]){
                    states[i][j+items[i]] = states[i-1][j];
                }
            }
        }

        int cur=-1;
        for(int i=manJian;i<=maxValue;i++){
            if(states[maxNum-1][i]){
                cur = i;
                break;
            }
        }
        if(cur<=-1){
            return;
        }
        for(int i=maxNum-1;i>=1;i--){
            if(cur-items[i]>=0&&states[i-1][cur-items[i]]==true){
                System.out.println(items[i]+"");
                cur = cur-items[i];
            }
        }
        if(items[cur]!=0){
            System.out.println(items[0]);
        }
    }
}
